package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: lynn
 * @Descript:  从尾到头打印链表
 * Question 4
 * @date: 2021/3/7 22:30
 * @version: 1.0
 */
public class Q4_PrintListFromTailToHead {

    public static void main(String[] args) {


      ListNode<Integer> listNode=new ListNode<Integer>(5);
        listNode.next=new ListNode(6);
        listNode.next.next=new ListNode(9);
        listNode.next.next.next=new ListNode(11);

        //常规方法
        System.out.println("=======常规方法输出链表=======");
        ListNode reverseNode=reverse(listNode);
        printNodeList(reverseNode);
        System.out.println();

        //递归
        System.out.println("=======递归方法输出链表=======");
        ListNode originNode=reverse(reverseNode);
        List<Integer> list=new ArrayList<>();
        list=reverseRecurse(list,originNode);
        list.stream().forEach(v-> System.out.print(v+" "));
    }



    private static class  ListNode<T> {
        private T data;
        private ListNode next;
        public ListNode(T data) {
            this.data = data;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }

    // 常规反转
    private static ListNode reverse(ListNode listNode){
        ListNode preNode=null;
        ListNode curNode=listNode;

        while (curNode!=null){
            ListNode nextNode=curNode.getNext();
            curNode.setNext(preNode);
            preNode=curNode;
            curNode=nextNode;
        }
        return preNode;
    }

    //递归反转
    private static List reverseRecurse (List arrayList,ListNode listNode){

        //使用递归时，先写递归终止的条件
        if (listNode==null){
            return arrayList;
        }
        reverseRecurse(arrayList,listNode.next);
        arrayList.add(listNode.data);
        return arrayList;
    }

    private static void printNodeList(ListNode listNode){
        ListNode curNode=listNode;
        while (curNode!=null){
            System.out.print(curNode+" ");
            curNode=curNode.getNext();
        }
    }
}
